package lanQiaoBei;

public class Heap1 {
    public static void main(String[] args) {
        Heap1 heap1 = new Heap1(10);
        heap1.insert(2);
        heap1.insert(4);
        heap1.insert(5);
        heap1.insert(3);
        heap1.insert(1);
//        heap1.insert(2);
//        heap1.insert(4);
//        heap1.insert(5);
//        heap1.insert(3);
//        heap1.insert(1);
        for (int i : heap1.getHeap()) {
            System.out.print(i+" ");
        }
        int modify = heap1.modify(2,4 );
        System.out.println("----");
        System.out.println(modify);
        for (int i : heap1.getHeap()) {
            System.out.print(i+" ");
        }
    }

    private int capacity;
    private int N;
    int[] heap;

    Heap1(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity + 1];
        N = 0;
    }
    public int[]getHeap(){
        return heap;
    }
    public int modify(int i, int num) {
        if (i > N) return -1;
        heap[i] = num;
        int swim = swim(i);
        int sink = sink(i);
        return swim == i ? sink : swim;
    }

    public int[] heapSort() {
        while (N >= 1) {
            delMax();
        }
        return heap;
    }

    public int delMax() {
        int r = heap[N];
        heap[N] = heap[1];
        heap[1] = r;
        N--;
        sink(1);
        return r;
    }

    private int sink(int i) {
        int son = i << 1;
        while (son <= N) {
            if (son + 1 <= N && heap[son + 1] > heap[son]) {
                son += 1;
            }
            if (heap[son] > heap[i]) {
                swap(son, i);
            } else break;
            i = son;
            son = i << 1;
        }
        return i;
    }

    public boolean insert(int num) {
        if (N >= capacity + 1) return false;
        heap[++N] = num;
        swim(N);
        return true;
    }

    private int swim(int i) {
        int p = i >> 1;
        while (p > 0) {
            if (heap[i] > heap[p]) {
                swap(i, p);
            } else {
                break;
            }
            i = p;
            p = i >> 1;
        }
        return i;
    }

    private void swap(int i, int p) {
        int temp = heap[i];
        heap[i] = heap[p];
        heap[p] = temp;
    }
}
